public class Solution4 {
    //91. 解码方法
    public int numDecodings(String ss) {
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n];
        if (s[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];
        if (s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if (t >= 10 && t <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            if (s[i] >= '1' && s[i] <= '9') dp[i] += dp[i-1];
            int tt = (s[i-1] - '0') * 10 + s[i] - '0';
            if (tt >= 10 && tt <= 26) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n-1];
    }
}
